1. Field of the Invention
The present invention relates to the design of computer systems that support objects defined within an object-oriented programming system. More specifically, the present invention relates to a method and an apparatus for maintaining an object-based write barrier to facilitate garbage collection operations in a computer system that provides an object-addressed memory hierarchy.
2. Related Art
As object-oriented programming languages become more widely used, computer systems are being designed to manipulate objects more efficiently. Along with manipulating objects, computer systems also manipulate ancillary structures associated with objects. For example, each object in an object-oriented programming system is typically associated with an object table entry that contains metadata associated with the object, such as the object's physical address (if the object has one).
Computer systems that support objects also maintain various structures to support garbage collection operations to reclaim objects that are no longer being used. In order to support generational garbage collection, the object heap is often partitioned into two or more partitions. Furthermore, the computer system typically maintains a write barrier between partitions to facilitate garbage-collection operations on a given partition. To accomplish this, some computer systems use a card table to keep track of modified values in other partitions that may potentially point to objects in a target partition being collected. In these computer systems, each partition can be divided up into equal-sized areas referred to as “cards.” Each time a portion of an object is modified within a card, a corresponding entry for the card is marked in the card table. Thus, during subsequent garbage collection operations, the system scans the card table looking for entries that are marked. If such an entry is found, the system scans the object in the corresponding memory card to identify references to the target area being collected. These references are used as “roots” for a subsequent garbage-collection operation.
While this method of maintaining a write barrier between partitions is effective, it has a rather high overhead. Each store to the object heap involves performing a corresponding store to mark the corresponding card table entry. Hence, each store operation becomes two stores. Furthermore, since bit operations can be rather time-consuming, the card table typically uses bytes or words rather than bits to represent cards. Consequently, the card table can take up a lot of space. Moreover, scanning the card table takes linear time, therefore increasing the size of the card table linearly increases the scanning time. This can become problematic as the heap becomes increasingly large.
Hence what is needed is a method and an apparatus for maintaining an object-based write barrier to facilitate garbage-collection operations without the problems described above.